#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums)
    {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n));

        unordered_map<long long, vector<int>> hash;
        for (int i = 0; i < n; i++) hash[nums[i]].push_back(i);

        int sum = 0;
        for (int j = 2; j < n; j++)
        {
            for (int i = 1; i < j; i++)
            {
                long long x = (long long)2 * nums[i] - nums[j];
                if (hash.count(x))
                {
                    for (auto index : hash[x])
                    {
                        if (index < i)
                            dp[i][j] += dp[index][i] + 1;
                        else break;
                    }
                }
                sum += dp[i][j];
            }
        }

        return sum;
    }
};